package com.learn.window;

import java.util.LinkedList;

/**
 * 求解小于指定数的子数组个数
 */
public class AllLessSubArr {
    public int getResult(int[] arr, int num) {
        if (arr == null || arr.length < 1) {
            return 0;
        }

        //维护最大值的队列
        LinkedList<Integer> qMax = new LinkedList<>();
        LinkedList<Integer> qMin = new LinkedList<>();
        int L = 0;
        int R = 0;
        int res = 0;
        int length = arr.length;
        while (L < length) {
            while (R < length) {
                if (!qMax.isEmpty() && arr[R] >= arr[qMax.peekFirst()]) {
                    qMax.pollLast();
                }
                qMax.addLast(R);

                if (!qMin.isEmpty() && arr[R] <= arr[qMin.peekFirst()]) {
                    qMin.pollLast();
                }
                qMin.addLast(R);


                if (arr[qMax.peekFirst()] - arr[qMin.peekFirst()] > num) {
                    break;
                }
                R++;
            }

            //当上述循环退出，代表已经出现不合规的子数组，统计以L为起始点，满足条件的子数组数量
            res += R - L;
            if (qMax.peekFirst() == L) {
                qMax.pollFirst();
            }

            if (qMin.peekFirst() == L) {
                qMin.pollFirst();
            }


            L++;

        }


        return res;
    }
}
